interface Queue<T> {
    // 将一个元素放入队列的尾部。
    fun push(i: T);

    //从队列首部移除元素。
    fun pop(): T;

    // 返回队列首部的元素。
    fun peek(): T;

    //返回队列是否为空。
    fun empty(): Boolean;
}

class MyQueue<T> : Queue<T> {
    //原始栈
    private var stack: Stack<T> = Stack()

    //迁移的栈
    private var cacheStack: Stack<T> = Stack()

    //如果连续的取数据
    private var flag = false

    override fun push(i: T) {
        if (cacheStack.isNotEmpty()) {
            stack.push(cacheStack.pop())
        }
        flag = false
        stack.push(i)
    }


    override fun pop(): T {
        return if (flag) {
            cacheStack.pop()
        } else {
            //数据翻转移到cacheStack
            while (stack.isNotEmpty()) {
                cacheStack.push(stack.pop())
                flag = true
            }
            cacheStack.pop()
        }
    }

    override fun peek(): T {
        return if (flag) {
            cacheStack.peek()
        } else {
            //数据翻转移到cacheStack
            while (stack.isNotEmpty()) {
                cacheStack.push(stack.pop())
                flag = true
            }
            cacheStack.peek()
        }
    }
    
    override fun empty(): Boolean {
        return stack.empty() && cacheStack.empty()
    }


}

fun main() {
    var myQueue = MyQueue<Int>()


    myQueue.push(1)
    myQueue.push(2)
    myQueue.push(3)
    myQueue.push(4)
    myQueue.push(5)
    myQueue.push(5)



    println(myQueue.peek())
    println(myQueue.pop())
    println(myQueue.pop())
    println(myQueue.pop())
    println(myQueue.pop())
    println(myQueue.pop())


    print(myQueue.empty())


}
